I.B.1. Introduction
Built-in self-test is a test technique that gives circuits the ability to test themselves. Test vectors (also called test patterns), comprising of a set of inputs to the circuit, are applied to the circuit under test (CUT). The responses of the CUT to the applied test vectors are compared with expected responses that correspond to a good circuit. A test pattern generator (TPG) generates test patterns.
BIST can be classified into test-per-clock (parallel) and test-per-scan (scan based) according to the way in which the test vectors are applied to the CUT. In test-per-clock BIST, the test patterns that are output from TPG are directly connected to the inputs of a CUT. A new test pattern is applied at every test clock cycle. In contrast, in scan-based BIST, the test patterns generated by a TPG are applied to the CUT through a scan chain that comprises flip-flops. Therefore, in scan-based BIST, a test pattern is applied to a CUT every m+1 cycles, where m is the number of flip-flops in the scan chain.
Random test pattern generators generate test patterns randomly. Test patterns can also be generated a priori and stored in a BIST for use during testing. In contrast to built-in self-test implemented with stored pattern generators that require high hardware overhead due to memory required to store deterministic test patterns, BIST implemented with pseudo-random pattern generators, require very little hardware overhead. Linear feedback shift registers (LFSR's) and cellular automata (CA) are two commonly used pseudo-random pattern generators.
Furthermore, it has been observed that random pattern test sequences generated by LFSR's or CAR's achieve higher coverages of unmodeled faults than stored test patterns. Additionally, the number of stored test patterns is typically very short due to stringent memory size constraints. However, some circuits require prohibitively long sequences of random patterns to achieve satisfactory fault coverage.
The random pattern test length required to achieve high fault coverage is often determined by only a few hard-to-detect faults. These hard-to-detect faults are also called random pattern resistant faults because they escape detection by most random patterns. Each of these random pattern resistant faults has very low detection probability, which is defined as the probability that a randomly generated vector detects the fault. See P. H. B., W. H. McAnney, and J. Savir. Built-In Test for VLSI: Pseudorandom Techniques, John Wiley & Sons, 1987. The detection probability of fault f can be defined as follows:                                           total            ⁢                                                   ⁢            number            ⁢                                                   ⁢            of            ⁢                                                   ⁢            tests            ⁢                                                   ⁢            for            ⁢                                                   ⁢            f                                2            m                          ,                            (        1        )            where m is the number of circuit inputs.
This implies that the hard-to-detect faults have many necessary input assignments that must be made for their detection. Hence, the probability that a randomly generated vector satisfies all the necessary input conditions is low.
Certain practitioners have proposed BIST techniques to improve detection probabilities of hard-to-detect faults that can be classified as extreme cases of conventional weighted random pattern testing (WRPT) BIST. See S. Pateras and J. Rajski, Cube-Contained Random Patterns and Their Application to the Complete Testing of Synthesized Multi-level Circuits, in Proceedings IEEE International Test Conference, pages 473-482, 1991; I. Pomeranz and S. Reddy, 3-Weight Pseudo-Random Test Generation Based on a Deterministic Test Set for Combinational and Sequential Circuits, IEEE Trans. On Computer-Aided Design of Integrated Circuit and System, Vol. 12:1050-1058, July 1993; and M. F. AlShaibi and C. R. Kime, Fixed-Biased Pseudorandom Built-In Self-Test For Random Pattern Resistant Circuits, in Proceedings IEEE International Test Conference, pages 929-938, 1994.
For further background information on (WRPT) BIST, see D. Neebel and C. R. Kime, Multiple Weighted Cellular Automata, in VLSITS, pages 81-86, 1994; H.-J. Wunderlich, Multiple Distributions for Biased Random Test Patterns, in Proceedings IEEE International Test Conference, pages 236-244, 1988; and R. Kapur, S. Patil, T. J. Snethen, and T. W. Williams, Design of an Efficient Weighted Random Pattern Generation System, in Proceedings IEEE International Test Conference, pages 491-500, 1994.
In the discussed techniques to improve detection probabilities of hard-to-detect faults, only three weights, 0, 0.5, 1, are assigned to each input, while various weights, e.g. 0, 0.25, 0.5, 0.75, 1.0, can be assigned in conventional WRPT. Since only three weights are used, the circuit to generate weights is simple; weight 1 (0) is obtained by fixing a signal to a 1. Likewise, weight 0 is obtained by fixing a signal to a 0. Weight 0.5 is obtained by driving a signal by an output of a pure random pattern generator, such as an LFSR. Furthermore, since only three weights are used, the size of memory required to store a weight set is also smaller than that of the conventional WRPT.
The present disclosure teaches techniques that use an improved automatic test pattern generator (ATPG) to minimize hardware overhead and test sequence length in 3-weight WRPT. In addition, this disclosure also teaches at least three improved BIST architectures that are implemented using the disclosed techniques for ATPG.
I.B.2. Notations and Definitions
In the present disclosure, the notations used in S. Pateras et al, are reused with few modifications. For detailed information on these notations, see S. Pateras and J. Rajski, Cube-Contained Random Patterns and Their Application to the Complete Testing of Synthesized Multi-level Circuits, In Proceedings IEEE International Test Conference, pages 473-482, 1991.
A testcube for a fault is defined as a test that has unspecified inputs. Let C={c1, c2, . . . , ch} denote a set of testcubes for hard-to-detect faults in a circuit under test (CUT), where cj={C1j, C2j, . . . , Cmj} is an m-bit testcube and where m is the number inputs of the CUT. Cij ε {0, 1, X}∀i and X is don't care. Let C1, C2, . . . , Cd be subsets of C and let generator, gen(Ci) {g1i,g2i, . . . , gmi} (i=1, 2, . . . , d) denote m-bit tuple where gki ε{0, 1, X, U} (k=1, 2, . . . , m) that is defined as follows:                               g          k          i                =                  {                                                    1                                                                                                        if                      ⁢                                                                                           ⁢                                              c                        k                        j                                                              =                                                                  1                        ⁢                                                                                                   ⁢                        or                        ⁢                                                                                                   ⁢                        X                        ⁢                                                                                                   ⁢                                                  ∀                                                                                    c                              j                                                        ∈                                                                                          C                                i                                                            ⁢                                                                                                                           ⁢                              and                              ⁢                                                                                                                           ⁢                              at                              ⁢                                                                                                                           ⁢                              least                              ⁢                                                                                                                           ⁢                              one                              ⁢                                                                                                                           ⁢                                                              c                                k                                j                                                                                                                                                        =                      1                                                        ⁢                                                                                                                                             0                                                                                  if                    ⁢                                                                                   ⁢                                          c                      k                      j                                                        =                                                            0                      ⁢                                                                                           ⁢                      or                      ⁢                                                                                           ⁢                      X                      ⁢                                                                                           ⁢                                              ∀                                                                              c                            j                                                    ∈                                                                                    C                              i                                                        ⁢                                                                                                                   ⁢                            and                            ⁢                                                                                                                   ⁢                            at                            ⁢                                                                                                                   ⁢                            least                            ⁢                                                                                                                   ⁢                            one                            ⁢                                                                                                                   ⁢                                                          c                              k                              j                                                                                                                                            =                    0                                                                                                      U                                                                                                        if                      ⁢                                                                                           ⁢                                              ∃                                                  c                          k                          a                                                                                      =                                                                  1                        ⁢                                                                                                   ⁢                        and                        ⁢                                                                                                   ⁢                                                  c                          k                          b                                                                    =                      0                                                        ,                                      where                    ⁢                                                                                   ⁢                                          c                      a                                                        ,                                                            c                      b                                        ∈                                          C                      2                                                                                                                          X                                                              otherwise                  .                                                                                        (        2        )            
It should be noted that the term generator is the same as weight sets used in D. Neebel and C. R. Kime. Multiple Weighted Cellular Automata, in VLSITS, pages 81-86, 1994; H.-J. Wunderlich. Multiple Distributions for Biased Random Test Patterns, in Proceedings IEEE International Test Conference, pages 236-244, 1988; and R. Kapur, S. Patil, T. J. Snethen, and T. W. Williams. Design of an Efficient Weighted Random Pattern Generation System, in Proceedings IEEE International Test Conference, pages 491-500, 1994.
When gki=U, there are testcubes in Ci that conflict at input pk, i.e. ∃a, b such that cka=v and ckb={overscore (V)} (v ε{1,0}) so that fixing input pk to a binary value v may make faults that require input pk to be assigned {overscore (ν)} undetectable. On the other hand, when gki=X, input pk is not specified in any testcube in Ci. Hence, in this case, input pk can be fixed to any binary value without losing fault coverage. The set of inputs that are assigned binary values in testcube cj but assigned U in the corresponding position in the generator gen(Ci) are called conflicting bits of cj. FIG. 1, shows example testcubes. In the set of testcubes shown in FIG. 1(a), c1 has 3 conflicting bits since inputs p1, p3, and p6 are assigned different binary values (0 or 1) in C1-C4. Therefore these pins are assigned U in gen(C). On the other hand, c2 has only one conflicting bit since only p3 among the inputs whose corresponding bits are assigned U in gen(C) is assigned a binary value 0 in c2.
a) Detection Probabilities
Let F={f1, f2, . . . fn} be the set of faults and C={c1, c2, . . . cn} be the set of testcubes. Assume that testcube cj, (j=1, 2, . . . n) is the only testcube for the corresponding fault, fj (j=1, 2, . . . n). Under this assumption, the detection probability of fault fj is merely ½m−|xj|, where m is the number of inputs and |Xj| is the number of inputs in testcube cj that are assigned don't care, X.
Let testcubes c1, c2, c3, and c4 shown in FIG. 1(a) be the only testcubes corresponding to faults f1, f2, f3, and f4 respectively. Testcubes c1, c2, c3, and c4 have 2, 2, 3, and 1 don't care values, respectively. Since each testcube is the only testcube for the corresponding fault, the detection probabilities of f1, f2, f3, and f4 can be respectively computed as ½4, ½4, ½3, and ½5 (note that the number of inputs, m, is 6 in this example).
As explained in Equation 2, if input pk is assigned either 1 or X in all testcubes in C and assigned 1 in at least one testcube, then it is assigned weight 1, i.e. gk=1. Likewise, if input pk is assigned either 0 or X in all testcubes in C and assigned 0 in at least one testcube, then it is assigned weight 0, i.e. gk=0. On the other hand, if gk is assigned a 1, then input pk can be fixed to a 1 to improve, by factor of 2, the detection probability of all faults in F that require the application of a 1 at pk for their detection. Similarly, if gk is assigned a 0, then input pk can be fixed to a 0 to improve, by factor of 2, the detection probability of all faults in F that require the application of a 0 at pk for their detection.
Since none of faults in F require the assignment of a 0 at pk for their detection, fixing pk to a 1 does not make any faults untestable. Similarly, since none of faults in F require the assignment of a 1 at pk for their detection, fixing pk to a 0 does not make any faults untestable.
In FIG. 1(a),if p2 is fixed to a 0, the detection probability of faults f2 and f4 both of which require the assignment of a 0 at p2 for their detection, increases to ½3 and ½4, respectively. In the same fashion, p4 and p5 can be fixed to a 1 and a 0, respectively. On the other hand, fixing other inputs p1, p3, and p6 to a binary value make some faults untestable since testcubes for these faults have conflicting values at these inputs. For example, fixing p1 to a 0 makes faults f3 and f4 untestable since they require the assignment of a 1 at p1 for their detection.
If the four testcubes c1, c2, c3, and c4 are partitioned into two groups C1={c1, c2} and C2={c3,c4}, inputs p1,p2,p4, p5, and p6 in C1 can respectively be fixed to 0, 0, 1, 0, and 1 and inputs p1,p2,p3, and p5 in C2 to 1, 0, 0, and 0 without any conflict. Since p4 is assigned X in all testcubes in C2 (c3 and c4), g42 is assigned X in gen(C2). As a consequence, gen(C1)={0, 0, U, 1,0,1,} and gen(C2)={1,0,0,X,0,U}. The detection probabilities of f1 and f2 are increased to ½ by fixing inputs p1,p2,p4,p5, and p6 to 0, 0, 1, 0, and 1, and the detection probabilities of f3 and f4 also are increased to ½ by fixing inputs p1,p2,p3, and p5 to 1, 0, 0, and 0. In order to apply two generators gen(C1) and gen(C2), inputs p1,p2,p4, and p5 are fixed to 0, 0, 1, and 0 for the first time interval T1 and then inputs p1,p2,p3, and p5 are fixed to 1, 0, 0, and 0 for the next time interval T2. The procedure to compute these time intervals is described in Section IVC.
b) Importance of Generating Appropriate Testcubes
Assume that f1 in FIG. 1(b) can be also detected by testcube c′1=0111XX and c′1 is used instead of c1 to compose testcube set C′1. Then, the 1 at p2 of c′1 conflicts with 0's at p2 of the other testcube c2 in C′1. Hence, only p1, p4, p5, and p6 can be fixed without conflict in C′1. Since only p1, p4, p5, and p6 are fixed, the detection probabilities of f2, which require 0 at p2 for detection, now become ½2—a factor of 2 decrease compared with when c1 is used. If the detection probabilities of all faults in F are to be improved to ½ or higher, then C′1 should be partitioned into two smaller groups each of which has only one member, c′1 and c2, respectively. Hence, three generators instead of two generators, which are required when c1 is used, are required when c′1 is used.
In order to minimize the number of generators required, which determines hardware overhead to implement the disclosed BIST, each testcube that is added to a testcube set should be selected carefully. The newly added testcube needs to be selected such that it has the minimum number of conflicting inputs with the other testcubes that already exist in the testcube set. However, it is known that the number of all possible testcubes for hard-to-detect faults may be large in large random pattern resistant circuits. Therefore, selecting a best testcube, which has the minimum number of conflicting inputs with the other testcubes in the testcube set, from a pool of all possible testcubes for each hard-to-detect fault will require prohibitively large time complexity. Hence, for such circuits, the number of generators required may depend significantly on testcubes selected to compose the testcube sets. This implies that testcubes for hard-to-detect faults should be carefully generated to build testcube sets that need the minimum number of generators.
c) Applying Generators to Circuit Inputs
In this sub-section, the idea of applying generators to the CUT is explained for the test-per-clock BIST. This information related to the test-per-clock BIST is provided as a background for a better understanding of the disclosed techniques related to the test-per-scan BIST, which is discussed in detail in Section IVD. Let inputs pk (k=1,2, . . . , m) be driven by corresponding random pattern signals rk (k=1, 2, . . . , m) during purely random pattern testing. While generator gen(Ci) is applied, input pk with gki=v is fixed to a binary value v by overriding random pattern signal rk by setting the corresponding overriding signal sk/v, to a 1. The overriding signal(s) for input pk is determined by values of gki (i=1, 2, . . . , d, where d is the number of generators). For instance, if gki (i=1, 2, . . . , d) are always assigned X or U in all d generators, input pk is not fixed in any generator and hence no overriding signal is required for pk. If gki are assigned a 1 or X and assigned a 1 in at least one generator, input pk should be fixed to a 1 while generator gen(Ci) in which gki=1 is applied. Similarly, if gki are assigned a 0 or X and assigned a 0 in at least one generator, input pk should be fixed to a 0 while generator gen(Ci) in which gki=0 is applied. If gk are assigned a 1 in gen(Ca) (i.e. gka=1) and 0 in gen(Cb) (i.e. gkb=0) input pk should be fixed to a 1 while generator gen(Ca) with gka=1 is applied and to a 0 while generator gen(Cb) with gkb=0 is applied.
To express the number of overriding signals and their overriding values for each input, glob_gen={gg1, gg2, . . . , ggm}, where m is the number of inputs and ggk (k=1,2, . . . , m) is introduced as follows:                               gg          k                =                  {                                                    1                                                                                                        if                      ⁢                                                                                           ⁢                                              g                        k                        i                                                              =                    1                                    ,                                                            U                      ⁢                                                                                           ⁢                      or                      ⁢                                                                                           ⁢                      X                      ⁢                                                                                           ⁢                                              ∀                        i                                                              =                    1                                    ,                  2                  ,                                                                           ⁢                  …                  ⁢                                                                           ,                                                            d                      ⁢                                                                                           ⁢                      and                      ⁢                                                                                           ⁢                      at                      ⁢                                                                                           ⁢                      least                      ⁢                                                                                           ⁢                      one                      ⁢                                                                                           ⁢                                              g                        k                        j                                                              =                    1                                                                                                      0                                                                                                        if                      ⁢                                                                                           ⁢                                              g                        k                        l                                                              =                    0                                    ,                                                            U                      ⁢                                                                                           ⁢                      or                      ⁢                                                                                           ⁢                      X                      ⁢                                                                                           ⁢                                              ∀                        i                                                              =                    1                                    ,                  2                  ,                  …                  ⁢                                                                           ,                                                            d                      ⁢                                                                                           ⁢                      and                      ⁢                                                                                           ⁢                      at                      ⁢                                                                                           ⁢                      least                      ⁢                                                                                           ⁢                      one                      ⁢                                                                                           ⁢                                              g                        k                        j                                                              =                    0                                                                                                      B                                                                                  if                    ⁢                                                                                   ⁢                                          ∃                                              g                        k                        a                                                                              =                                                            1                      ⁢                                                                                           ⁢                      and                      ⁢                                                                                           ⁢                                              g                        k                        b                                                              =                    0                                                                                                      N                                            otherwise                                                                        (        3        )            where d is the number of generators.
When ggk=v (vε{1, 0}), only one overriding signal sk/v is required for input pk and when ggk=B, two overriding signals sk/1 and sk/0 are required. Finally, when ggk=N, all gki (i=1, 2, . . . , d) are X's or U's, and input pk is always driven by random pattern signal rk during entire test application and hence no overriding signal is required for pk.
FIG. 2 shows the generators and overriding signals for a circuit with 5 inputs. Since input p1 is fixed to both a 1 (g10) and (g11 and g13), gg1 is assigned B and two overriding signals s1/0 and s1/1 are assigned to input p1. On the other hand, since input p3 is fixed to only a 1 (g31 and g33), gg3 is assigned a 1 and only one overriding signal s3/1 is assigned to p3. Finally, since g5i is assigned no binary value in any of generators gen(Ci) (i=1,2,3,4), input p5 is always driven by random pattern signal r5 without being fixed. Hence, gg5 is assigned N and no overriding signal is assigned to p5. In conclusion, since two inputs, p1 and p4, are assigned ggk=B (k=1,4) and input p2 and p3 are assigned gg2=0 and gg3=1, respectively. The generators shown in FIG. 2 that have glob_gen={B, 0,1, B, N}, require 6 overriding signals, s1/0, s1/1, s2/0, s3/1, s4/0, and s4/1.
FIG. 3 shows an implementation of 3-weight WRPT circuitry for a test-per-clock BIST for the generator and overriding signals shown in FIG. 2. Signals ri (i=1,2, . . . ,5) are connected to the outputs of a ramdom pattern generator. COUNTER in FIG. 3 selects the appropiate generator; if the content of COUNTER is i, generator gen(Ci) is selected. Each gen(Ci) is used to generate test patterns for Ti test cycles as described above. If gki=v(v=0 or 1), then input pk is fixed to a binary value v by overriding random pattern signal rk by setting the corresponding signal sk/v to a 1.
For example, while gen(C1)={0, X,1,1,U} is applied to the CUT, s1/0,s3/1, and s4/1 are set to a 1 to override random pattern signals r1, r3, and r4 while other overriding signals are assigned a 0. Signal ENABLE is used to enable or disable WRPT. When setting ENABLE to a 0 diables WRPT, none of the inputs are fixed and hence the random pattern generator drives all inputs. Since each state of COUNTER corresponds to a generator, the required number of bits of COUNTER is given by [log2(the number of generator)]. The overrriding signals are generated from DECODER shown in FIG. 3 with the outputs of COUNTER as inputs. The number of inputs and outputs typically determines the area required by DECODER. Hence, the number of overriding signals required to fix inputs as well as the number of generators determines the hardware overhead due to 3-weight WRPT.
The procedure described for the test-per-clock BIST are also applicable to the test-per-scan BIST (scan-based BIST) with little modification. Techniques to alter bit sequences that are scanned into a scan chain to detect hard-to-detect faults are proposed in, H.-J. Wunderlich and G. Kiefer. Bit-Flipping BIST,in Proceedings VLSI Testing Symposium, pages 337-343, 1996; and N. A. Touba and E. J. McCluskey, Altering a Pseudo-Random Bit Sequence for Scan-Based BIST, in Proceedings IEEE International Test Conference, pages 167-175, 1996 (Touba'96). Touba'96 uses the similar procedure that is used in Touba'95 to compute the mapping function that converts the complement of tests that detect any new faults into the tests for undetected faults. See N. A. Touba and E. J. McCluskey, Altering a Pseudo-Random Bit Sequence for Scan-Based BIST, In Proceedings IEEE International Test Conference, pages 167-175, 1996; and N. Touba and E. McCluskey, Synthesis of Mapping Logic for Generating Trans-formed Pseudo-Random Patterns for BIST, In Proceedings IEEE International Test Conference, pages 674-682, 1995. Since the procedure is highly dependent on the test sequence that is applied to the CUT, sometimes the complement of such tests can be tautology or in the other extreme case, the complement can have significant number of specified inputs leading to high hardware overhead. Furthermore, the whole BIST circuitry that alters the bit-sequence should be re-designed if the test sequence is changed. Karkala uses the same techniques as Touba'96 to convert pseudo-random sequences that do not detect any new faults to deterministic testcubes; See M. Karkala, N A. Touba, and H.-J. Wunderlich, Special ATPG to Correlate Test Patterns for Low-Overhead Mixed-Mode BIST, in proceedings 7γrd Asian Test Symposium, 1998; and N. A. Touba and E. J. McCluskey, Altering a Pseudo-Random Bit Sequence for Scan-Based BIST, in Proceedings IEEE International Test Conference, pages 167-175, 1996, However, unlike Touba'95, where deterministic testcubes are generated by a conventional ATPG procedure, in Karkala, deterministic testcubes are generated by a special ATPG that considers correlation among the deterministic BIST. See N. A. Touba and E. McCluskey, Synthesis of Mapping Logic for Generating Trans-formed Pseudo-Random Patterns for BIST, in Proceedings IEEE International Test Conference, pages 674-682, 1995; and M. Karkala, N A. Touba, and H.-J. Wunderlich, Special ATPG to Correlate Test Patterns for Low-Overhead Mixed-Mode BIST, In proceedings 7γrd Asian Test Symposium, 1998. H.-J. Wunderlich uses a procedure that is similar to Touba'96 but alters random patterns to deterministic pattern by flipping some bits of the random patterns. See H.-J. Wunderlich and G. Kiefer, Bit-Flipping BIST, in Proceedings VLSI Testing Symposium, pages 337-343, 1996; N. A. Touba and E. J. McCluskey, Altering a Pseudo-Random Bit Sequence for Scan-Based BIST, in Proceedings IEEE International Test Conference, pages 167-175, 1996. This technique is also highly dependent on the random pattern test sequence applied.
I.B.3. Conventional ATPG for a 3-weight WRPT BIST
In Pateras, a complete set of testcubes is generated for two-level version of synthesized circuits (the simple structure of two-level circuits makes generation of all tests possible). See S. Pateras and J. Rajski, Cube-Contained Random Patterns and Their Application to the Complete Testing of Synthesized Multi-level Circuits, in Proceedings IEEE International Test Conference, pages 473-482, 1991. These testcubes are partitioned into several sets such that the number of conflicting inputs of any testcube in each set is less than or equal to M and a generator is computed for each of the sets. Since the number of generators depends on testcubes in the testcube sets, as described in I.B.2(b), testcubes that have many necessary assignments are filtered out to reduce the number of generators required. This is because, if testcubes in the set have many necessary assignments, there will be more conflicting inputs and hence fewer testcubes can be placed in each testcube set leading to more generators. Hence testcubes that have fewer necessary assignments can be included in the testcube sets to be used to create generators. However, the testcubes for two-level circuits may contain testcubes that are not necessary for their multi-level synthesized circuits.
According to the experimental results reported in S. Pateras, this filtering procedure requires very high time complexity (the run time of this procedure is typically higher than that of synthesis procedure). See S. Pateras and J. Rajski, Cube-Contained Random Patterns and Their Application to the Complete Testing of Synthesized Multi-level Circuits, in Proceedings IEEE International Test Conference, pages 473-482, 1991. However, this procedure is believed to be necessary in this method to choose good testcubes (testcubes that has few necessary assignments) from complete set of testcubes. Since this method requires a complete set of testcubes, applying this method to large circuits, whose two-level versions are not available, may not be possible due to prohibitively high time complexity.
As is clear, the present teaching is aimed at overcoming the problems described above in general and providing improved techniques.